package com.origin.niuke.dfs;

import java.util.ArrayList;
import java.util.Arrays;

/**
 * @author yzh
 * @version 1.0
 * @date 2022/6/13 21:36
 * 有重复项数字的全排列
 * 算法：深度优先搜索
 */
public class NC42 {

    public ArrayList<ArrayList<Integer>> permuteUnique(int[] num) {
        Arrays.sort(num);
        boolean[] used = new boolean[num.length];
        ArrayList<ArrayList<Integer>> ans = new ArrayList<>();
        dfs(used, num, new ArrayList<>(), ans);
        return ans;
    }

    void dfs(boolean[] used, int[] num, ArrayList<Integer> list, ArrayList<ArrayList<Integer>> ans) {
        if (list.size() == num.length) {
            ans.add(new ArrayList<>(list));
            return;
        }
        for (int i = 0; i < num.length; i++) {
            if (used[i]) continue;
            if (i != 0 && num[i] == num[i - 1] && !used[i - 1]) continue;
            list.add(num[i]);
            used[i] = true;
            dfs(used, num, list, ans);
            used[i] = false;
            list.remove(list.size() - 1);
        }
    }

}
